package 链表;

/**
 * <p>
 * https://leetcode-cn.com/problems/remove-linked-list-elements/
 * 删除链表中等于给定值 val 的所有节点。
 * </p>
 *
 * @author AJun
 * @since 2020/8/12
 */
public class _203_移除链表元素 {

    // 删除头结点时另做考虑
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val)
            head = head.next;

        if (head == null)
            return null;

        ListNode curr = head;
        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }

        }
        return head;
    }

    // 添加一个虚拟头结点(哨兵位)
    public ListNode removeElements1(ListNode head, int val) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode prev = sentinel; // 前一个节点
        while (prev.next != null) {
            if (prev.next.val == val)
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }
        return sentinel.next; // 返回去除哨兵位的链表
    }

    // 递归
    public ListNode removeElements2(ListNode head, int val) {
        if (head == null)
            return null;

        head.next = removeElements2(head.next, val);
        return head.val == val ? head.next : head;
    }

}
